Counting extensions in random graphs

Abstract: We consider rooted subgraphs in random graphs, i.e., extension counts such as (a) the number of triangles containing a given `root' vertex, or (b) the number of paths of length three connecting two given `root' vertices.

In 1989 Spencer gave sufficient conditions for the event that, whip, all roots of the binomial random graph G(n,p) have the same asymptotic number of extensions, i.e., (1 \pm \epsilon) times their expected number.

For the important strictly balanced case, Spencer also raised the fundamental question whether these conditions are necessary.

We answer this question by a careful second moment argument, and discuss some intriguing problems that remain open.

Joint work with Matas Sileikis, see arXiv:1911.03012

combinatoricsprobability

Audience: researchers in the topic

( paper )

Comments: Password: the first 6 prime numbers (8 digits in total)

---

Extremal and probabilistic combinatorics webinar

Series comments: We've added a password: concatenate the 6 first prime numbers (hence obtaining an 8-digit password).

---